# 给定一个二叉树，检查它是否是镜像对称的。 
# 
#  
# 
#  例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 
# 
#      1
#    / \
#   2   2
#  / \ / \
# 3  4 4  3
#  
# 
#  
# 
#  但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 
# 
#      1
#    / \
#   2   2
#    \   \
#    3    3
#  
# 
#  
# 
#  进阶： 
# 
#  你可以运用递归和迭代两种方法解决这个问题吗？ 
#  Related Topics 树 深度优先搜索 广度优先搜索 
#  👍 1353 👎 0


from typing import List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:

        def check(left: TreeNode, right: TreeNode):
            if not left and not right:
                return True
            if not left or not right:
                return False
            return check(left.left, right.right) and check(left.right, right.left)

        return check(root, root)


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)

#      1
#    / \
#   2   2
#  / \ / \
# 3  4 4  3
"""
左右的值相等, 且1:左向左, 右向右 2: 左向右, 右向左 都对称
"""
# def isSymmetric(self, root: TreeNode) -> bool:
#     return self.check(root, root)
#
# def check(self, left: TreeNode, right: TreeNode):
#     if left is None and right is None:
#         return True
#     if left is None or right is None:
#         return False
#     return left.val == right.val and self.check(left.left, right.right) and self.check(left.right, right.left)

if __name__ == '__main__':
    s = Solution()
    t = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
    assert s.isSymmetric(t)
